package arrayandstring;

import java.util.Stack;
/**
 * https://leetcode-cn.com/problems/baseball-game/
 */
public class E682_BaseballGame {
    /**
     * 时间复杂度 O(n) 空间复杂度 O(n)
     */
    public int calPoints(String[] ops) {
        // temp[]存储数字模拟栈
        int[] temp = new int[ops.length];
        // temp[]的索引模拟栈顶指针
        int top = 0;
        int sum = 0;
        for (int i = 0; i < ops.length; i++) {
            String str = ops[i];
            switch (str) {
                case "+":
                    // 栈顶前两个数字之和存储在数组的下一个索引位置并且栈顶指针+1
                    temp[top] = temp[top-1] + temp[top-2];
                    sum += temp[top++];
                    break;
                case "D":
                    // 栈顶数字翻倍存储在数组的下一个索引位置并且栈顶指针+1
                    temp[top] = temp[top-1] << 1;
                    sum += temp[top++];
                    break;
                case "C":
                    // 减去栈顶的数字并且栈顶指针-1
                    sum -= temp[--top];
                    break;
                default:
                    // 数字入栈并且栈顶指针+1
                    temp[top] = Integer.parseInt(str);
                    sum += temp[top++];
                    break;
            }
        }
        return sum;
    }
    /**
     * 官方解法
     * 时间复杂度 O(n) 空间复杂度 O(n)
     * 在处理数据时保持栈上每个有效回合的值
     */
    public int calPoints1(String[] ops) {
        Stack<Integer> stack = new Stack<>();
        // 遍历数组并且栈中存储有效值
        for (String op : ops) {
            if ("+".equals(op)) {
                // pop()返回栈顶元素且在栈中移除该元素
                // peek()返回栈顶元素但在栈中不移除该元素
                int temp = stack.pop();
                int newtop = temp + stack.peek();
                stack.push(temp);
                stack.push(newtop);
            } else if ("C".equals(op)) {
                // 移除栈顶元素
                stack.pop();
            } else if ("D".equals(op)) {
                // 栈顶元素两倍的值入栈
                stack.push(2*stack.peek());
            } else {
                stack.push(Integer.valueOf(op));
            }
        }
        // 遍历栈
        int sum = 0;
        for (Integer score : stack) {
            sum += score;
        }
        return sum;
    }
}
